home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / LISP / AUTOCLAS / DOC / DESIGN.TEX (.txt) < prev    next >
LaTeX Document  |  1990-07-17  |  7KB  |  117 lines
  1. ;;; -*- Mode: TEXT -*-
  2. ;;; File:  AutoClass:doc;Design.text
  3. ;;;--------------------------------------------------------------------------;;;
  4. ;;;  AUTOCLASS 3.0  Released 5/11/90    contact:  Taylor@pluto.arc.nasa.gov  ;;;
  5. ;;;  by P. Cheeseman, J. Stutz, R. Hanson, W. Taylor                  ;;;
  6. ;;;  NASA Ames Research Center, MS 244-17, Moffett Field, CA 94035           ;;;
  7. ;;;                                                                          ;;;
  8. ;;;  Copyright (C) 1990 Research Institute for Advanced Computer Science.    ;;;
  9. ;;;  All rights reserved.  The RIACS Software Policy contains specific       ;;;
  10. ;;;  terms and conditions on the use of this software, and must be           ;;;
  11. ;;;  distributed with any copies.  THIS FILE MAY BE REDISTRIBUTED.  This     ;;;
  12. ;;;  copyright and notice must be preserved in all copies made of this file. ;;;
  13. ;;;--------------------------------------------------------------------------;;;
  14. This file gives an intermediate level description of the AutoClass-3 program
  15. design.  It was originally generated as an informal system specification and
  16. development notebook.
  17. Objectives:
  18. 1 - A modular implementation of the likelihood function that allows easy
  19. extension of the set of attribute interactions that can be described.  This
  20. contrasts with AutoClass 2 in which the single interaction type (conditional
  21. independence) was built into the code, and the only alternative was to ignore
  22. some attributes.
  23. 2 - User specification of the current likelihood function, or class model, at
  24. run time.  This is envisioned as being a product of conditionally independent
  25. likelihood terms over selected data attributes.  The user chooses the type of
  26. interaction, for specific sets of attributes, from a range of prespecified
  27. interaction types.
  28.     Note that this probably pays too little attention to the problem of
  29. searching the model space.  In the block covariant normal there are many
  30. combinations of blocks possible.
  31. 3 - Minimize runtime by compiling the class likelihood function into a single
  32. function over the class parameters and a datum's attributes. This has been
  33. extended to a variety of class specific functions.
  34. 4 - For developmental flexibility it is desired to:
  35.     a - Be able to maintain multiple classifications. 
  36.     b - Be able to maintain multiple models.
  37. 5 - To support future research it is desired to:
  38.     a - Define classifications that contain multiple class
  39. likelihood models.
  40.     b - Define hierarchical models capable of runtime optimization.
  41. Constraints:
  42. 1 - The range of the calculated probabilities forces us to perform our
  43. calculations in terms of logarithms.  Probability normalization may then result
  44. in underflow, and produce nominal zeros.
  45. Terminology:
  46.     I will speak of probability and likelihood distribution functions
  47. interchangeably.  They are in fact exactly the same function form, used to
  48. calculate the probability of data with respect to fixed parameters or the
  49. likelihood of parameters with respect to a fixed set of data.
  50. Implementation:
  51.     A classification is defined in terms of the probability model(s) and
  52. classes which instantiate the model(s). The classification is made with respect
  53. to some particular database.  A classification is implemented as a
  54. classification-$ structure (short name is clsf-$) which contains several
  55. parameters, a database pointer, a vector of model pointers, and an adjustable
  56. fill-pointer vector of class pointers. See the files ..>prog>struct-model.lisp,
  57. ..>prog>struct-clsf.lisp, and ..>prog>struct-class.lisp.  Models,
  58. classifications, and classes are implemented in an object oriented manner using
  59. Common Lisp structures with supplementary functions having the same prefix as
  60. the corresponding structure accessors.
  61.     A probability model is defined in terms of attribute interactions for a
  62. particular database.  The model partitions the attributes into subsets (type
  63. att-set-$) whose members interact according to a particular probability
  64. function term.  Within the model, the subsets are assumed to be conditionally
  65. independent (given the class).  Thus the inter-set probabilities are
  66. multiplicatively combined and the model specifies a probability function term
  67. for each att-set.  The model also defines the parameter structure of instance
  68. classes, provides the priors, and holds the names of the runtime compiled model
  69. dependent functions (log-likelihood, update-xxxx, &etc.) used for generic
  70. operations on it's classes.  A user specifies the model in an xxx.model file
  71. that is interpreted by functions on the ..>prog>i/o-read-model file.  The
  72. runtime definition of model/database specific functions is carried out by
  73. invocation of the expand-model-terms function and the expand-xxx-fn functions
  74. in file ..>prog>model-expander.
  75.     The probability function terms specify how the element(s) of an attribute
  76. subset interact to produce a probability.  Addition of a new probability term
  77. type requires specification of priors,the parameter structures, and a set of
  78. functions for the likelihood term, the class statistics based likelihood and
  79. marginal term approximations, and certain auxiliary terms.  Runtime model
  80. expansion will then produce a set of model specific class functions which call
  81. the appropriate probability terms with precompiled arguments.  See the files
  82. ..>prog>model-xxx.lisp, particularly ..prog>model-expander.  The currently
  83. defined probability terms are single-multinomial, single-normal-cn (for
  84. Constant observation error, No missing values), and single-normal-cm (for
  85. Constant observation error, Missing values present).
  86.     A class is an instance of a likelihood model within a
  87. classification.  It consists of:
  88.     a. Structures instantiating the parameter set (and auxiliary
  89. variables) of the model.
  90.     b. Functions to reference the model dependent functions.
  91.     c. A vector of the class weights (probabilities) for each datum.
  92.     d. Various class specific parameters.
  93. See file ...>prog>struct-class.lisp.
  94.     A data-base contains descriptive information and a vector of data instance
  95. vectors of attribute values.  The information consists of the source file(s)
  96. name(s), the number of instances (n-data), number of attributes (n-atts), and
  97. an 'att-info vector.  There is a positional correspondence between the
  98. 'att-info vector and the data instance vectors. The elements of 'att-info give
  99. the data type (one of *att-types*), a documentation string, and type dependent
  100. range information (see real-range-$ and disc-range-$).  Two data bases are
  101. considered equivalent, relevant to a particular model, if all referenced
  102. attributes have the same type and missing value, and discrete types have the
  103. same range. The database input functions are in file i/o-read-data.lisp.
  104. Databases are stored on a file pair: an xxx.db2 file which contains the number
  105. of data and object vectors, and an xxx.hd2 file containing the object
  106. descriptions.
  107. Files
  108. All files of the development system are in Autoclass:....  The program files
  109. are in Autoclass:program;, data files in Autoclass:data; and experimental
  110. results in Autoclass:results; The program is implemented as a system under the
  111. name of autoclass with short name of ac in package ac. The system declaration
  112. file is ...>prog>sys-dcl.lisp.  Generally those files forming a system module
  113. will have names with a common prefix.
  114. Operation:
  115. See file ...>usage.text for current information on preparing, running,
  116. and interpretation of AutoClass.
  117.